%% $Id: xygraph.doc,v 2.12 1994/10/25 11:34:25 kris Exp $
%% XY-pic ``Graph Combinator feature'' option.
%% Copyright (c) 1994		Kristoffer H. Rose	<kris@diku.dk>
%% This file is part of the XY-pic package for graphs and diagrams in TeX.
%% See the companion README and INSTALL files for further information.
%% Copyright (c) 1991-1994	Kristoffer H. Rose	<kris@diku.dk>
%% The XY-pic package is free software; you can redistribute it and/or modify
%% it under the terms of the GNU General Public License as published by the
%% Free Software Foundation; either version 2 of the License, or (at your
%% option) any later version.
%% The XY-pic package is distributed in the hope that it will be useful, but
%% WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
%% or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
%% for more details.
%% You should have received a copy of the GNU General Public License along
%% with this package; if not, write to the Free Software Foundation, Inc.,
%% 675 Mass Ave, Cambridge, MA 02139, USA.
\ifx\xyloaded\undefined \input xy \fi
\xyprovide{graph}{Graph Combinator feature}{\stripRCS$Revision: 2.12 $}%
 {Kristoffer H.~Rose}{kris@diku.dk}%
 {Computer Science, University of Copenhagen, Universitetsparken~1,
  DK--2100 K{\o}benhavn~{\O}}
\DOCMODE3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	This option implements `\XY-graph', a special "combinatoric drawing
	language" suitable for diagrams like flow charts, directed graphs,
	and various forms of trees.  The base of the language is reminiscent
	of the PIC~\cite{K82:PIC-LTG} language because it uses a notion of
	the `current location' and is based on `moves'.  But the central
	construction is a `map' combinator that is borrowed from functional
	programming.
\DOCMODE2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph*{Header:}\leavevmode
\DOCHEADER
\DOCMODE3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\XY-graph make use of facilities of the `arrow' feature option which
	is therefore required.
\DOCMODE(
\xyrequire{arrow}\xycatcodes
\DOCMODE)
\DOCMODE3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	Figure~??[f.graph] summarises the syntax of a <graph> with notes
	below.  A <graph> can appear either in an \XY-picture (as <decor>) or
	``stand-alone''.
\begin{figure*}[tb]
\begin{syntax}
 \multispan{3}{{\tt\string\xygraph\string{<graph>\string}}\hfil}
	& typeset <graph>
\noalign{\nobreak\smallskip\nobreak\hrule\nobreak\smallskip\nobreak}
 ??w![<graph>]
  &\iss	& <step>\star
	& interpret <step>s in sequence
\noalign{\smallskip}
 ??w![<step>]
  &\iss	& <node>
	& ??!^[move] to the <node>
  &\orr	& |-| <node> <labels>
	& ??!^[draw] line to <node>, with <labels>
  &\orr	& |:|<arrow> <node> <labels>
	& ??!^[draw] <arrow> to <node>, with <labels>
  &\orr	& |(| <list> |)|
	& ??!^[map] current node over <list>
\noalign{\smallskip}
 ??w![<node>]
  &\iss	& |[| <move> |]|
	& new node <move>d relative to current
  &\orr	& |"|<id>|"|
	& previously ??!^[saved] node
  &\orr	& |?|
	& currently ??!^[mapped] node
  &\orr	& |!| <escape>
	& interpret material in another mode
  &\orr	& <node> <it>
	& <node> with <it> ??!^[typeset and saved] there
  &\orr	& <node> |=| |"|<id>|"|
	& <node> ??!^[saved] as |"|<id>|"|
\noalign{\smallskip}
 ??w![<move>]
  &\iss	& <hop>\star\
	& ??!^[<hop>s] (|dulr|) from current node
\noalign{\smallskip}
 ??w![<list>]
  &\iss	& <graph> |,| <list> \orr\ <graph>
	& ??!^[list of subgraphs]
\noalign{\smallskip}
 ??w![<escape>]
  &\iss	& |{| <pos> <decor> |}|
	& ??!^[perform <pos> <decor>]
  &\orr	& |M| <matrix>
	& ??!^[insert <matrix>]
  &\orr	& |P| <matrix>
	& ??!^[insert <polygon>]
\end{syntax}
\caption{\protect<graph>s}??=[f.graph]
\end{figure*}
\DOCMODE2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph*{Parsing:}
	The parser does almost everything that this feature does because it
	is all implemented directly on top of other constructions, notably
	the kernel stack and the <arrow> construction:
\DOCMODE(
\xydef@\xygraph#1{\relax \if\inxy@ \DN@{\xy@@{\nter@{}}}%
 \else \DN@{\addGT@{\addLT@\xy 0ex,.8ex}\xy@\xy{\nter@\endxy}}\fi \next@
 \xy@\xygraph{\senter@ \idfromc@{?NODE}%
  \expandafter\let\expandafter\next@\csname Q@graphbase\endcsname
  \ifx\next@\relax \setbase@\z@\z@{3pc}\z@
  \else \expandafter\next@ \fi}%
 \xyFN@\GRAPH@ #1\GRAPH@}
\xydef@\GRAPH@{%
 \ifx \space@\next \expandafter\DN@\space{\xyFN@\GRAPH@}%
 \else\ifx :\next \DN@:{\xy@:{}\GRAPHarr@}%
 \else\addDASH@\ifx\next \addDASH@\DN@{\addAT@{\xyFN@\GRAPH@:}{-}}%
 \else\ifx (\next \DN@({\xy@({\spushc@ \idfromc@{?NODE}}\xyFN@\GRAPH@}%
 \else\ifx ,\next
  \DN@,{\xy@,{\if\sempty@ \xyerror@{, only allowed in <list>}{}\fi
    \cfromid@{?NODE}}\xyFN@\GRAPH@}%
 \else\ifx )\next
  \DN@){\xy@){\if\sempty@ \xyerror@{) only allowed after (}{}\fi
    \cfromid@{?NODE}\spop@ \idfromc@{?NODE}}\xyFN@\GRAPH@}%
 \else\ifx \GRAPH@\next \DN@\GRAPH@{\xy@@{\sleave@\leave@}}%
 \else\ifx ~\next
  \DN@~{\xy@@{\enter@\cfromthec@}\afterNODE{\leave@ \xyFN@\GRAPH@}!}%
 \else \DN@{\afterNODE{\xyFN@\GRAPH@}}%
 \fi\fi\fi\fi\fi\fi\fi\fi \next@}
\xylet@\GRAPHsaved@PATHafterPOS=\PATHafterPOS
\xylet@\GRAPHsaved@afterarr@@=\afterarr@@
\xydef@\GRAPHarr@{%
 \let\PATHafterPOS=\afterNODE \let\afterarr@@=\GRAPHafterarr@ \ar}
\xydef@\GRAPHafterarr@{%
 \let\PATHafterPOS=\GRAPHsaved@PATHafterPOS
 \let\afterarr@@=\GRAPHsaved@afterarr@@
 \xy@@{\lastNODE@@}\xyFN@\GRAPH@}
\xylet@\afterNODE@@=\empty
\xydef@\afterNODE#1{%
 \DN@##1{\def\afterNODE@@{\def\afterNODE@@{##1}#1}}%
 \expandafter\next@\expandafter{\afterNODE@@}%
 \xyFN@\NODE@}
\xylet@\lastNODE@@=\relax
\xylet@\theMOVE@@=\relax
\xydef@\NODE@{%
 \ifx \space@\next \expandafter\DN@\space{\xyFN@\NODE@}%
 \else\ifx "\next \DN@ "##1"{\xy@{"##1"}{\cfromid@{##1}}\xyFN@\NODE@i}%
 \else\ifx ?\next \DN@ ?{\xy@?{\cfromid@{?NODE}}\xyFN@\NODE@i}%
 \else\ifx [\next \DN@[##1]{\xy@{[##1]}{}\def\theMOVE@@{[##1]}\xyFN@\MOVE@##1]}%
 \else\ifx !\next \DN@!{\xyFN@\NODE@escape}%
 \else \xyerror@{illegal <node>}{}%
 \fi\fi\fi\fi\fi \next@}
\xydef@\MOVE@{\xy@@{\count@=\z@ \count@@=\z@}%
 \ifx \space@\next \expandafter\DN@\space{\xyFN@\MOVE@}%
 \else\ifcat A\next \let\next@=\MOVE@letter
 \else \let\next@=\MOVE@x \fi\fi \next@}
\xydef@\MOVE@letter{%
 \ifx \space@\next \expandafter\DN@\space{\xyFN@\MOVE@letter}%
 \else\ifx u\next \DN@ u{\xy@@{\advance\count@\@ne}\xyFN@\MOVE@letter}%
 \else\ifx d\next \DN@ d{\xy@@{\advance\count@\m@ne}\xyFN@\MOVE@letter}%
 \else\ifx l\next \DN@ l{\xy@@{\advance\count@@\m@ne}\xyFN@\MOVE@letter}%
 \else\ifx r\next \DN@ r{\xy@@{\advance\count@@\@ne}\xyFN@\MOVE@letter}%
 \else \let\next@=\MOVE@x \fi\fi\fi\fi\fi \next@}
\xydef@\MOVE@x{%
 \ifx ]\next
  \DN@ ]{\xy@@{\czeroEdge@ \enter@\cplusthec@
    \edef\next@{\the\count@@,\the\count@ @}%
    \expandafter\vfromcartesian@@\next@
    \advance\Xc-\Xorigin \advance\Yc-\Yorigin \leave@}\xyFN@\NODE@i}%
 \else \xyerror@{illegal <move>: \theMOVE@@}{}\let\next@=\NODE@i
 \fi \next@}
\xydef@\NODE@i{%
 \ifx \space@\next \expandafter\DN@\space{\xyFN@\NODE@i}%
 \else\ifcat A\noexpand\next \let\next@=\NODE@it
 \else\ifx \bgroup\next \let\next@=\NODE@it
 \else\ifx *\next \let\next@=\NODE@it
 \else\ifx 0\next \let\next@=\NODE@it
 \else\ifx 1\next \let\next@=\NODE@it
 \else\ifx 2\next \let\next@=\NODE@it
 \else\ifx 3\next \let\next@=\NODE@it
 \else\ifx 4\next \let\next@=\NODE@it
 \else\ifx 5\next \let\next@=\NODE@it
 \else\ifx 6\next \let\next@=\NODE@it
 \else\ifx 7\next \let\next@=\NODE@it
 \else\ifx 8\next \let\next@=\NODE@it
 \else\ifx 9\next \let\next@=\NODE@it
 \else\addEQ@\ifx \next
  \addEQ@\DN@"##1"{\xy@{="##1"}{\idfromc@{##1}}\xyFN@\NODE@i}%
 \else \xy@@{\edef\lastNODE@@{\cfromthec@}}\let\next@=\afterNODE@@
 \fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi \next@}
\xydef@\NODE@it{\let\PATHlabelit@@=\NODEit@ \PATHit@}
\xydef@\NODEit@#1{%
 \DN@{#1}\ifx\next@\empty \DN@{\addPLUS@\NODEit@i}%
 \else \DN@{\NODEit@i{#1}}\fi \next@}
\xydef@\NODEit@i#1#2{\xy@{*#1{#2}}{\drop@{#1}{#2}\idfromc@{#2}}\xyFN@\NODE@i}
\DOCMODE)
\DOCMODE3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{notes}
\note??=[move]
	A "move" is to establish a new "current node".
\note??=[draw]
	To "draw" something is simply to draw a line or the specified <arrow>
	from the current node to the specified target node.  The target then
	becomes the current node.  All the features of arrows as described
	in~\S??g[:arrow] can be used, in particular arrows can be labelled and
	segmented, but with the change that <path-pos> means <node> as
	explained in note~\S??g[xyarrow.doc:segment].
\note??=[map]??=[mapped]??=[list of subgraphs]
	To "map over a list" is simply to save the current node and then
	interpret the <list> with the following convention:
\begin{itemize}
\item Start each element of the list with the current node as saved and $p$
	as the previous list element, and
\item let the |?| <node> refer to the saved current node explicitly.
\end{itemize}
\note??=[typeset and saved]??=[saved]
	Typeset <it> and make it the current node.  Also saves <it> for later
	reference using |"|<id>|"|: if <it> is a simple letter, or digit,
	then just as |"|<it>|"|; if <it> is of the form
	|{|"text"|}| or |*|\dots|{|"text"|}| then as |"|"text"|"|.
	With the |=| addition it is possible to save explicitly in case
	several nodes have the same text or a node has a text that it is
	impractical to use for reference.
\begin{exercise}
	How did the author typeset this?
\begin{code}
\xygraph{
 []A="A1" :@/^.5pc/ [r]A
	  :@/^.5pc/ [r]A
	  :@/^1pc/ "A1" }
\end{code}
$$\docode$$
\answercode
\answertext{The first $A$ was named to allow reference from the last:
	\displaycode}
\end{exercise}
\note??=[<hop>s]
	Moving by a series of "hops" is simply moving in a grid as the
	sequence of |dulr| (for down/up/left/right) indicates.  The grid is a
	standard cartesian coordinate system with 3pc unit unless a base
	|"graph|\-|base"| is defined or the current base is redefined using
	|!| with an appropriate <pos>ition using |:| and |::| as described in
	note~??g[xy.doc:base].
	\TODO: Many more moves should be allowed, in particular these should
	be available: (1)~`until perpendicular to \dots' and (2)~`until
	intercepts with \dots'.
\note??=[perform <pos> <decor>]
	This `escapes' into the \XY-pic kernel language and interprets the
	<pos> <decor>.  The current node is then set to the resulting $c$
	object and the grid from the resulting "base".
	The effect of the <pos> <decor> can be completely hidden from
	\XY-graph by entering it as |{\save|\dots|\restore}|.
\DOCMODE(
\xydef@\NODE@escape{%
 \ifx \space@\next \expandafter\DN@\space{\xyFN@\NODE@escape}%
 \else\ifx M\next \DN@ M##1##{\NODE@matrix{##1}}%
 \else\ifx P\next \DN@ P##1##{\NODE@poly{##1}}%
 \else\ifx \bgroup\next
  \DN@##1{\xy@{!{##1}}{}\POS##1\relax \xyFN@\NODE@i}%
 \else \DN@{\xyerror@{Unknown graph <escape>}{}\xyFN@\NODE@i}%
 \fi\fi\fi\fi \next@}
\DOCMODE)
\note??=[insert <matrix>]
	\NOTE: This only works when the `matrix' feature has also been
	loaded.  It inserts a node consisting of the <matrix> which must have
	the usual form (see~\S??g[:matrix] for the details):
\begin{defs1}
 <rotation> |{| <rows and columns> |}|
\end{defs1}
\noindent\unskip
	Within the matrix the following two control sequences are specially
	defined: |\:| is defined as an alias for |\ar| and |\="|<id>|"|
	will save the entry as |"|<id>|"| (|\everyentry| is used for these).
	Finally the grid is set as the top left `square' of the matrix, \ie,
	with |[d]| and |[r]| adjusted as they work in the top left entry (so
	|[dr]| immediately after the matrix will work as expected, \eg, make
	the center of |"2,2"| the current node, but others might not, \eg,
	|[rr]| will not necessarily place the current node on top of |"1,3"|.
\note??=[insert <polygon>]
	\NOTE: This only works when the `polygon' feature has also been
	loaded.  It inserts a node consisting of the <polygon> which must have
	the usual form (see~\S??g[:poly] for the details).
\DOCMODE2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	The code is straight forward except we use the undocumented
	|\everymatrix@@| hook\dots
\DOCMODE(
\xydef@\NODE@matrix#1#2{\xyerror@{matrix feature not loaded}{}\xyFN@\GRAPH@}
\xydef@\NODE@matrix@#1#2{\xy@{!M#1{#2}}{}%
 \def\everyentry@{\GRAPHeveryentry}%
 \xymatrix#1{#2}%
 \let\everyentry@=\empty \insertmatrixingraph@ \xyFN@\NODE@i}
\xydef@\GRAPHeveryentry{\def\:{\ar}\def\="##1"{\xy@@{\idfromc@{##1}}}}
\xywithoption{matrix}{\let\NODE@matrix=\NODE@matrix@}
\xydef@\insertmatrixingraph@{%
 \xy@@{\enter@{\cfromthec@ \pfromthep@}%
 \expandafter\let\expandafter\next@\csname Q@1,1\endcsname
 \ifx\next@\relax\else
  \next@ \swap@
  \expandafter\let\expandafter\next@\csname Q@1,2\endcsname
  \ifx\next@\relax\else \next@ \setbase@\Xp\Yp\Xc\Yc
   \expandafter\let\expandafter\next@\csname Q@2,1\endcsname
   \ifx\next@\relax\else
    \next@ \setbase@@{-\Xc}{-\Yc}\fi\fi\fi
 \leave@}}
\DOCMODE)
\DOCMODE3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\note??=[insert <polygon>]
	It is possible to insert a <polygon> in a graph provided the |poly|
	option described in~\S??g[:poly] has been loaded: it will have its
	center on top of the current node and default radius as the <hop>
	base size.
\DOCMODE(
\xydef@\NODE@poly#1#2{\xyerror@{poly(gon) feature not loaded}{}\xyFN@\GRAPH@}
\xydef@\NODE@poly@#1#2{\xy@{!P#1{#2}}{}\xypoly@#1{#2}\xyFN@\NODE@i}
\xywithoption{poly}{\let\NODE@poly=\NODE@poly@}
\DOCMODE)
\DOCMODE3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{notes}
	The canonical diagram example illustrates most of the above:
\begin{code}
\xygraph{
 !M{ X \times_Z Y \="xy" \:[r]_p \:[d]^q
		     & X \="X" \:[d]_f   \\
     Y \="Y" \:[r]^g & Z }
 [ul]U   ( ? :@/^.5pc/ ^x        "X" ,
	   ? :@{-->}   |-{(x,y)} "xy" ,
	   ? :@/_.5pc/ _y        "Y" )   }
\end{code}
\displaycode
\noindent
	typesets
\docode
\DOCMODE2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{End \& log}
\DOCMODE(
\xyendinput
% $Log: xygraph.doc,v $
% Revision 2.12  1994/10/25  11:34:25  kris
% Interim release just before v3 [works with AMS-LaTeX 1.2]...
% Revision 2.11  1994/07/05  10:37:32  kris
% Third 3beta release [bug fixes].
% Experimental graph feature included (for ECCT-94 presentation).
% New for v3...
\DOCMODE)
\DOCMODE3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Tell Emacs how we are formatted:
% Local Variables:
% mode:latex
% fill-prefix:"\t"
% fill-column:77
% paragraph-separate:"^[ \t\f]*$\\|^[^\t]\\|\\\\\\\\\\|\\$\\$\\|[^\n\\\\][%&]"
% paragraph-start:"^[ \t\f]*$\\|^[^\t]\\|\\\\\\\\\\|\\$\\$\\|[^\n\\\\][%&]"
% LaTeX-indent-level:1
% TeX-brace-indent-level:1
% End: